package cn.zifangsky.heap;

import java.util.Arrays;

/**
 * 二叉堆（最小堆）
 *
 * @author zifangsky
 * @date 2018/12/20
 * @since 1.0.0
 */
public class BinaryMinHeap<T extends Comparable<? super T>> implements BinaryHeap<T>{
    /**
     * 默认的堆大小
     */
    private static final int DEFAULT_INITIAL_CAPACITY = 16;

    /**
     * 当前最小堆存储的数量
     */
    private int size;

    /**
     * 存储数据的数组
     */
    private T[] array;

    public BinaryMinHeap() {
        this(DEFAULT_INITIAL_CAPACITY);
    }

    public BinaryMinHeap(int initialCapacity) {
        if (initialCapacity < 0) {
            throw new IllegalArgumentException("Illegal initial capacity: " +
                    initialCapacity);
        }

        this.array = (T[]) new Comparable[initialCapacity];
        this.size = 0;
    }

    public BinaryMinHeap(T[] initialArray) {
        if (initialArray == null) {
            throw new IllegalArgumentException("Illegal initial initialArray");
        }

        this.size = initialArray.length;
        this.array = (T[]) new Comparable[initialArray.length];

        for(int i = 0; i < initialArray.length; i++){
            array[i] = initialArray[i];
        }

        this.buildHeap();
    }

    /**
     * 返回当前二叉堆的数量
     */
    @Override
    public int size() {
        return size;
    }

    /**
     * 判断当前二叉堆是否为空
     * @author zifangsky
     * @date 2018/12/25 20:10
     * @since 1.0.0
     * @return boolean
     */
    @Override
    public boolean isEmpty() {
        return size == 0;
    }

    @Override
    public boolean contains(T data) {
        if(data != null){
            for(T temp : array){
                if(temp.equals(data)){
                    return true;
                }
            }
        }

        return false;
    }

    /**
     * 清空当前二叉堆
     * @author zifangsky
     * @date 2018/12/26 14:49
     * @since 1.0.0
     */
    @Override
    public void clear(){
        this.array = (T[]) new Comparable[size];
        size = 0;
    }

    /**
     * 插入
     * <p>思路：将新节点放在原来最后节点后面一个位置，然后再将这个新节点不断上浮到适当位置</p>
     * @author zifangsky
     * @date 2018/12/25 20:07
     * @since 1.0.0
     * @param data 待插入数据
     */
    @Override
    public void insert(Object data){
        //如果当前数组已满，则需要扩容
        if(size == array.length){
            this.resize();
        }

        //1. 将新节点放在原来最后节点后面一个位置
        int point = size;
        array[point] = (T) data;

        //2. 将这个新节点不断上浮到适当位置（如果point / 2 == 0，则表示新节点在右子树，否则在左子树）
        int parentIndex = (point / 2 == 0) ? ((point - 2) / 2) : ((point - 1) / 2);
        while (parentIndex >= 0 && array[point].compareTo(array[parentIndex]) < 0){
            //节点上浮
            array[point] = array[parentIndex];
            array[parentIndex] = (T) data;

            point = parentIndex;
            parentIndex = (point / 2 == 0) ? ((point - 2) / 2) : ((point - 1) / 2);
        }

        size++;
    }

    /**
     * 查找最小元素
     * @author zifangsky
     * @date 2018/12/26 14:49
     * @since 1.0.0
     * @return T
     */
    @Override
    public T getFirst(){
        if(isEmpty()){
            return null;
        }else{
            return array[0];
        }
    }

    /**
     * 删除根节点
     * <p>思路：将最后一个节点移到根节点，然后将当前根节点不断下浮到适当位置，最后将最后一个节点置空并返回原来的根节点</p>
     * @author zifangsky
     * @date 2018/12/25 20:08
     * @since 1.0.0
     * @return T
     */
    @Override
    public T deleteFirst(){
        if(isEmpty()){
            return null;
        }else{
            //标记一下原来的根节点
            T root = array[0];

            //1. 将最后一个节点移到根节点
            array[0] = array[size - 1];

            //2. 将当前根节点不断下浮到适当位置
            this.downAdjust(0);

            //3. 将最后一个节点置空
            array[size - 1] = null;
            size--;

            return root;
        }
    }

    @Override
    public Object[] toArray() {
        return Arrays.copyOf(this.array, this.size);
    }

    @Override
    public T[] toArray(T[] a) {
        final int size = this.size;
        if(a.length < size){
            return (T[]) Arrays.copyOf(this.array, size, a.getClass());
        }

        System.arraycopy(this.array, 0, a, 0, size);
        if (a.length > size) {
            a[size] = null;
        }
        return a;
    }

    /**
     * 将无序数组建立成二叉堆
     */
    private void buildHeap(){
        //遍历数组，平衡节点位置
        for(int i = (size - 1); i >= 0; i--){
            //下浮调整
            this.downAdjust(i);
        }
    }

    /**
     * 下浮调整
     * @param point 待调整的节点坐标
     */
    private void downAdjust(int point){
        //左孩子节点的索引
        int leftChildIndex = point * 2 + 1;
        //右孩子节点的索引
        int rightChildIndex = point * 2 + 2;

        //让所有不满足条件的非叶子节点依次下沉
        while ((leftChildIndex < size && array[point].compareTo(array[leftChildIndex]) > 0)
                || (rightChildIndex < size && array[point].compareTo(array[rightChildIndex]) > 0)){
            //只有左孩子节点或者左孩子节点小于右孩子节点，当前节点跟左孩子节点交换
            if(rightChildIndex >= size || array[leftChildIndex].compareTo(array[rightChildIndex]) <= 0){
                T temp = array[leftChildIndex];
                array[leftChildIndex] = array[point];
                array[point] = temp;

                point = leftChildIndex;
            }
            //左孩子节点大于右孩子节点，当前节点跟右孩子节点交换
            else if(array[leftChildIndex].compareTo(array[rightChildIndex]) > 0){
                T temp = array[rightChildIndex];
                array[rightChildIndex] = array[point];
                array[point] = temp;

                point = rightChildIndex;
            }

            leftChildIndex = point * 2 + 1;
            rightChildIndex = point * 2 + 2;
        }
    }

    /**
     * 扩容数组
     */
    private void resize(){
        T[] old = array;
        //扩容两倍
        array = (T[]) new Comparable[old.length * 2];
        //转移原来的数据
        for(int i = 0; i < old.length; i++){
            array[i] = old[i];
        }
    }

}
